#include <iostream>
#include <cmath>
#define NIL -1
struct vEB{
int u, min=NIL, max=NIL;
vEB* summary;
vEB** cluster;
bool FN=false;
vEB(int _u): u(_u) {
if(this->u!=2){
int szC=static_cast<int>(std::ceil(std::sqrt(u)));
int szF=static_cast<int>(std::floor(std::sqrt(u)));
summary=new vEB(this->u/szC);
cluster=new vEB*[this->u/szC];
for(int i=0; i<this->u/szC; ++i){
cluster[i]=new vEB(szF);
}
} else {
FN=true;
summary=nullptr; cluster=nullptr;
}
}
~vEB(){
if(!FN){
int szC=static_cast<int>(std::ceil(std::sqrt(u)));
for(int i=0; i<szC; ++i) delete cluster[i];
delete summary;
delete[] cluster;
}
}
int High(int x){
return x/static_cast<int>(std::sqrt(this->u));
}
int Low(int x){
return x%static_cast<int>(std::sqrt(this->u));
}
int Index(int x, int y){
return x*static_cast<int>(std::sqrt(u))+y;
}
int Minimum(void){
return this->min;
}
int Maximum(void){
return this->max;
}
bool Member(int x){
if(x==this->min || x==this->max) return true;
else if(this->u==2) return false;
else return cluster[this->High(x)]->Member(this->Low(x));
}
int Successor(int x){
if(this->u==2){
if(x==0 && this->max==1) return 1;
else return NIL;
}
else if(this->min!=NIL && x<this->min) return this->min;
else {
int max_low=this->cluster[High(x)]->Maximum();
if(max_low!=NIL && Low(x)<max_low){
int offset=this->cluster[High(x)]->Successor(Low(x));
return Index(High(x), offset);
} else {
int succ_cluster=this->summary->Successor(High(x));
if(succ_cluster==NIL) return NIL;
else {
int offset=this->cluster[succ_cluster]->Minimum();
return Index(succ_cluster, offset);
}
}
}
}
int Predecessor(int x){
if(this->u==2){
if(x==1 && this->min==0) return 0;
else return NIL;
} else if(this->max!=NIL && x>this->max) return this->max;
else {
int min_low=this->cluster[High(x)]->Minimum();
if(min_low!=NIL && Low(x)>min_low){
int offset=this->cluster[High(x)]->Predecessor(Low(x));
return Index(High(x), offset);
} else {
int pred_cluster=this->summary->Predecessor(High(x));
if(pred_cluster==NIL){
if(this->min!=NIL && x>this->min) return this->min;
else return NIL;
} else {
int offset=this->cluster[pred_cluster]->Maximum();
return Index(pred_cluster, offset);
}
}
}
}
void EmptyInsert(int x){
this->min=x;
this->max=x;
}
void Insert(int x){
if(this->min==NIL) EmptyInsert(x);
else{
if(x<this->min){
int tmp=x;
x=this->min;
this->min=tmp;
}
if(this->u>2){
if(this->cluster[High(x)]->Minimum()==NIL){
this->summary->Insert(High(x));
this->cluster[High(x)]->EmptyInsert(Low(x));
} else {
this->cluster[High(x)]->Insert(Low(x));
}
}
if(x>this->max) this->max=x;
}
}
void Delete(int x){
if(this->min==this->max){
this->min=NIL;
this->max=NIL;
} else if(this->u==2){
if(x==0) this->min=1;
else this->min=0;
this->max=this->min;
} else {
if(x==this->min){
int first_cluster=this->summary->Minimum();
x=Index(first_cluster, this->cluster[first_cluster]->Minimum());
this->min=x;
}
this->cluster[High(x)]->Delete(Low(x));
if(this->cluster[High(x)]->Minimum==NIL){
this->summary->Delete(High(x));
if(x==this->max){
int summary_max=this->summary->Maximum();
if(summary_max==NIL){
this->max=this->min;
} else {
this->max=Index(summary_max, this->cluster[summary_max]->Maximum());
}
}
} else if(x==this->max){
this->max=Index(High(x), this->cluster[High(x)]->Maximum());
}
}
}
};
int main(void){
vEB* vanEB=new vEB(16);
int set[]={2, 3, 4, 5, 7, 14, 15};
for(int i=0; i<sizeof(set)/sizeof(int); ++i){
vanEB->Insert(set[i]);
}
vanEB->Delete(7);
vanEB->Delete(4);
std::cout<<vanEB->Minimum()<<std::endl;
std::cout<<vanEB->Maximum()<<std::endl;
std::cout<<vanEB->Predecessor(14)<<std::endl;
std::cout<<vanEB->Successor(3)<<std::endl;
delete vanEB;
return 0;
}